package previous.Test_0205;

import java.util.Arrays;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
  class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
public class Solution {
    //计算布尔二叉树的值
    public boolean evaluateTree(TreeNode root) {
        if (root.left == null && root.right == null) {
            if (root.val == 0) {
                return false;
            } else {
                return true;
            }
        }
        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val == 2 ? left | right : left & right;
    }

    //求根节点到叶节点数字之和
    public int sumNumbers(TreeNode root) {
        return sum(root, 0);
    }

    public int sum(TreeNode root, int presum) {
        presum = presum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return presum;
        }
        int ret = 0;
        if (root.left != null) {
            ret += sum(root.left, presum);
        }
        if (root.right != null) {
            ret += sum(root.right, presum);
        }
        return ret;
    }

    //二叉树剪枝
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        root.left=pruneTree(root.left);
        root.right=pruneTree(root.right);
        if (root.left==null && root.right==null && root.val == 0)
            root = null;
        return root;
    }
    //验证二叉搜索树
    long prev=Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        boolean left=isValidBST(root.left);
        if(left==false) return false;
        boolean cur=false;
        if(prev<root.val){
            cur=true;
        }
        prev=root.val;
        boolean right=isValidBST(root.right);
        if(right==false) return false;
        return left && cur && right;
    }
    //判断字符是否唯一
    public boolean isUnique(String astr) {
        if(astr.length()>26){
            return false;
        }
        int bit=0;
        for (int i = 0; i <astr.length(); i++) {
            int x=astr.charAt(i)-'a';
            if((bit>>x&1)==1){
            return false;
            }
            bit|=1<<x;

        }
        return true;
    }
    //丢失的数字
    public int missingNumber1(int[] nums) {
        int n=nums.length;
        int[] s=new int[n];
        for (int i = 0; i < n; i++) {
            s[i]=i;
        }
        Arrays.sort(nums);
        for (int i = 0; i <n ; i++) {
            int ret=nums[i]^s[i];
            if(ret!=0){
                return i;
            }
        }
        return n;
    }
    //消失的数字
    public int missingNumber(int[] nums) {
        int ret=0;
        for (int i = 0; i < nums.length; i++) {
            ret^=nums[i];
        }
        for (int i = 0; i <= nums.length; i++) {
            ret^=i;
        }
        return ret;
    }
    //两数之和
    public int getSum(int a, int b) {
        int ret=a^b;
        int r=(a&b)<<1;
        return ret+r;
    }
    public int getSum1(int a,int b){
        while(b!=0){
            int ret=a^b;
            int r=(a&b)<<1;
            a=ret;
            b=r;
        }
        return a;
    }
    //只出现一次的数字

}
